3. 10pts total.  each operation 1pt.
for those of you using the C book, this is a quicksort problem:
I'm giving a solution that strictly follows the procedures in the book, some variations in median of 3 are allowed. Some of you didn't stop i or j from increasing or decreasing when the value pointed to is equal to the pivot, note this is correct only if you check whether i or j are falling off the boundaries. otherwise, they could grow beyond the array.
Another mistake some of you are making is that you don't advance i and j after a swap. This will cause problems if both of values i and j are pointing to are equal to the pivot and you swap them, now what you should do is tomove both of i and j before comparing the values they are pointing to to the pivot, if you don't, you end up with an infinite loop swapping the two values and never go forward. you were taken off 2 pts if you made this mistake.
original:                             3    1    4    1    5    9    2    6    5    3    5
after median of 3:              3    1    4    1    5    3    2    6    5    5    9       pivot is 5,  it's swapped with the 3 in the second to last position.
                                        i                                                      j             start qsort with the current positions of i and j
swaps:                              3    1    4    1    5    3    2    6    5    5    9      swap 5 and 5
                                                                 i                       j
                                        3    1    4    1    5    3    2    5    5    6    9      swap pivot and 6
                                                                            j      i
the right half will be sorted as 5 6 9 with insertion sort because of cutoff of 3.
the left half:                       3    1    4    1    5    3    2
after median of 3              1    1    4    3    5    2    3                pivot is 2
                                        i                             j
swaps:                             1    1     2    3    5    4    3                swap 4 with pivot
                                              j      i
the left half is sorted with insertion sort.
the right half                                        3    5    4    3
after median of 3                                 3    4    3    5            pivot is 3
                                                           i            j
swaps:                                                3    3     4    5           swap pivot and 4
                                                          j      i
finally the sequence is 1,1,2,3,3,4,5,5,5,6,9

for those of you using the C++ book, this is merge sort problem.
Here's the solution by Katja Borchert(I think. If I'm wrong, apologies and please email me)


 

4. 10 pts total. 1pt/2entries.
                    Insertion         Bubble        Shell                Heap            Merge            Quick
Sorted            O(N)            O(N)        O(N^3/2)*      O(NlogN)    O(NlogN)            **

Reversed        O(N^2)       O(N^2)     O(N^3/2)      O(NlogN)    O(NlogN)            **

Random          O(N^2)       O(N^2)    O(N^3/2)       O(NlogN)    O(NlogN)        O(NlogN)
 

*: both O(N) and O(NlogN) are acceptable depending on what increments sequence you choose.
**: depends on the pivot selection. if the first or last element is selected as pivot, then both Sorted and Reversed will have the worst-case running time O(N^2). If median of 3 is used, then they are both the best case which is O(NlogN).